home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 2 / AACD 2.iso / AACD / WebSites / MailingLists / AMOSLIST.0599 / 000020_nobody_Wed May 5 06:34:36 1999.msg < prev    next >
Internet Message Format  |  1999-06-01  |  2KB
  1. Received: from onelist.com (pop.onelist.com [209.207.164.227])
  2.     by osf1.gmu.edu (8.8.8/8.8.8) with SMTP id GAA03311
  3.     for <mcox4@osf1.gmu.edu>; Wed, 5 May 1999 06:34:35 -0400 (EDT)
  4. Received: (qmail 23491 invoked by alias); 5 May 1999 10:34:45 -0000
  5. Received: (qmail 23415 invoked from network); 5 May 1999 10:34:43 -0000
  6. Received: from unknown (HELO saintolaves.demon.co.uk) (195.99.45.122) by pop.onelist.com with SMTP; 5 May 1999 10:34:43 -0000
  7. Date: Wed,  5 May 1999 11:38:55 EST
  8. Message-Id: <199905051138.AA363331878@saintolaves.demon.co.uk>
  9. From: <cheila@saintolaves.demon.co.uk>
  10. X-Sender: <cheila@saintolaves.demon.co.uk>
  11. To: amos-list@onelist.com
  12. X-Mailer: <IMail v4.06>
  13. Mailing-List: list amos-list@onelist.com; contact amos-list-owner@onelist.com
  14. Delivered-To: mailing list amos-list@onelist.com
  15. Precedence: bulk
  16. List-Unsubscribe: <mailto:amos-list-unsubscribe@ONElist.com>
  17. Reply-to: amos-list@onelist.com
  18. Mime-Version: 1.0
  19. Content-Type: text/plain; charset=us-ascii
  20. Subject: Re: [amos-list] Crossing lines, fast.
  21. Status: O
  22. X-Status: 
  23.  
  24. From: <cheila@saintolaves.demon.co.uk>
  25.  
  26. Hi
  27.  
  28. Here is a nice algorithm to check if line segments cross:
  29.  
  30. Input:
  31.  
  32. Line1: x0,y0 - x1,y1 
  33. Line2: u0,v0 - u1,v1
  34. (with _1 >= _0)
  35.  
  36. Step 1: Check bounding boxes
  37.  
  38. if u0 > x1 then not cross
  39. if u1 < x0 then not cross
  40. if v0 > y1 then not cross
  41. if v1 < y0 then not cross
  42.  
  43. Step 2: Check cross
  44.  
  45. line1: x = x1*t + (1-t)*x0, y = y1*t + (1-t)*y0
  46. line2: x = u1*s + (1-s)*u0, y = v1*s + (1-s)*v0
  47.  
  48. solve for s, t (simultaneous equations, simple)
  49. if 0 <= t <= 1 and 0 <= s <= 1 then cross
  50.  
  51. Step 3: Find intersection (may not be needed)
  52.  
  53. substitute t or s to find x, y
  54.  
  55.  
  56. I think this is one of the best algorithms, but there may
  57. be some more.  There are more complicated versions for
  58. polygons in 3D (if that's what you're doing).
  59.  
  60. Hope this helps
  61.  
  62. Claude
  63.  
  64.  
  65. ------------------------------------------------------------------------
  66. Wanting to get back in touch with old friends?
  67. http://www.onelist.com
  68. Reunite through a ONElist community.
  69. ------------------------------------------------------------------------
  70. Official AMOS WWW: http://members.xoom.com/AmosFactory/front.html